#include <iostream>
#include <utility>
#include <list>
#include <unordered_map>

using std::cout;
using std::endl;
using std::pair;
using std::list;
using std::unordered_map;

class LRU
{
public:
    LRU(int capa)
    : _capa(capa)
    {
    }

    void put(int key, int value)
    {
        auto it = _um.find(key);
        if(it != _um.end())//存在list
        {
            it->second->second = value;//更新value
            //更新元素key-value在list中的位置
            _nodes.splice(_nodes.begin(), _nodes, it->second);
        }
        else//不存在list中
        {
            //检查是否为满
            if(_capa == _nodes.size())
            {
                //在list删除最后一个元素之前，需要将其保留一下
                //只有这样才能将最后一个元素从unordered_map
                //中删除
                auto deleteNode = _nodes.back();
                //从um中删除
                _um.erase(deleteNode.first);
                _nodes.pop_back();//删除最后一个节点
            }
            //将key-value插入到list最前面
            _nodes.push_front({key, value});
            //将key与key在list中的位置插入到um中
            _um[key] = _nodes.begin();
        }
    }

    int get(int key)
    {
        auto it = _um.find(key);
        if(it == _um.end())
        {
            return -1;
        }
        else
        {
            //更新元素key-value在list中的位置
            _nodes.splice(_nodes.begin(), _nodes, it->second);
            return it->second->second;
        }
    }

    void print() const
    {
        for(auto &elem : _nodes)
        {
            cout << "(" << elem.first
                 <<", " << elem.second
                 << ")" << "  ";
        }
        cout << endl;
    }
private:
    int _capa;//存放节点的个数
    list<pair<int, int>> _nodes;//节点
    unordered_map<int, list<pair<int, int>>::iterator> _um;//key与key在list中的位置
};
void test()
{
    LRU lru(3);

    lru.put(1, 10);
    lru.print();

    cout << endl;
    lru.put(2, 20);
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;
    lru.print();

    cout << endl;
    lru.put(3, 30);
    lru.print();

    cout << endl;
    lru.put(4, 40);
    lru.print();

    cout << endl;
    lru.put(3, 33);
    lru.print();

    cout << endl;
    lru.put(2, 20);
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;
    lru.print();
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}

